package com.leetcode.partition6;

import java.util.HashSet;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2021/11/1 12:01
 */
public class LC523连续的子数组和 {

    public static boolean checkSubarraySum(int[] nums, int k) {
        return prefixSum(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {23, 2, 4, 6, 7};
        int k = 24;
        System.out.println(checkSubarraySum(nums, k));
    }

    private static boolean prefixSum(int[] nums, int k) {
        int[] prefix = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) prefix[i] = prefix[i - 1] + nums[i - 1];
        //若(prefix[j]-prefix[i])%k==0，则prefix[j]%k==prefix[i]%k
        Set<Integer> remainderSet = new HashSet<>();
        //prefix[j]始终比prefix[i]大，保证了最少两个元素，也可以使用HashMap，key为余数，value为索引，通过余数得到索引，并判断索引差值是否大于等于2
        for (int j = 2; j < prefix.length; j++) {
            remainderSet.add(prefix[j - 2] % k);
            if (remainderSet.contains(prefix[j] % k)) {
                return true;
            }
        }
        return false;
    }
}
